# multiAgents.py
# --------------
# Licensing Information:  You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
# 
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).


from util import manhattanDistance
from game import Directions
import random, util

from game import Agent
from pacman import GameState

class ReflexAgent(Agent):
    """
    A reflex agent chooses an action at each choice point by examining
    its alternatives via a state evaluation function.

    The code below is provided as a guide.  You are welcome to change
    it in any way you see fit, so long as you don't touch our method
    headers.
    """


    def getAction(self, gameState: GameState):
        """
        You do not need to change this method, but you're welcome to.

        getAction chooses among the best options according to the evaluation function.

        Just like in the previous project, getAction takes a GameState and returns
        some Directions.X for some X in the set {NORTH, SOUTH, WEST, EAST, STOP}
        """
        # Collect legal moves and successor states
        legalMoves = gameState.getLegalActions()

        # Choose one of the best actions
        scores = [self.evaluationFunction(gameState, action) for action in legalMoves]
        bestScore = max(scores)
        bestIndices = [index for index in range(len(scores)) if scores[index] == bestScore]
        chosenIndex = random.choice(bestIndices) # Pick randomly among the best

        "Add more of your code here if you want to"

        return legalMoves[chosenIndex]

    def evaluationFunction(self, currentGameState: GameState, action):
        """
        Design a better evaluation function here.

        The evaluation function takes in the current and proposed successor
        GameStates (pacman.py) and returns a number, where higher numbers are better.

        The code below extracts some useful information from the state, like the
        remaining food (newFood) and Pacman position after moving (newPos).
        newScaredTimes holds the number of moves that each ghost will remain
        scared because of Pacman having eaten a power pellet.

        Print out these variables to see what you're getting, then combine them
        to create a masterful evaluation function.
        """
        successorGameState = currentGameState.generatePacmanSuccessor(action)
        newPos = successorGameState.getPacmanPosition()
        # 获取食物在图中的分布（二维数组，有失误为T没食物为F)
        newFood = successorGameState.getFood()
        newGhostStates = successorGameState.getGhostStates()
        # 获取吃超级豆子之后 Ghost害怕还剩余的时间
        newScaredTimes = [ghostState.scaredTimer for ghostState in newGhostStates]
        "*** YOUR CODE HERE ***"
         # 求出最近的鬼怪，计算危险值
        nearestGhost = min([manhattanDistance(newPos,ghostState.configuration.pos) for ghostState in newGhostStates])
        #取-20是为了把豆豆的启发值设置在10以内，两者相加一定为负数，这样就可以抵消豆豆对吃豆人的诱惑
        dangerScore = -20 if nearestGhost <2 else 0
        # 如果豆豆还没有吃光，用最近的豆豆的坐标用曼哈顿距离计算一个启发值，优先考虑吃掉最近的豆豆
        if len(newFood.asList())>0:
            nearestFood = (min([manhattanDistance(newPos, food) for food in newFood.asList()]))
            # 如果下一个豆豆就在隔壁，距离为1，那么启发值为9，且距离放在分母，其值越大，启发值就越小
            foodHeuristic = 9/nearestFood
        else:
            foodHeuristic = 0
        return successorGameState.getScore()+foodHeuristic+dangerScore



def scoreEvaluationFunction(currentGameState: GameState):
    """
    This default evaluation function just returns the score of the state.
    The score is the same one displayed in the Pacman GUI.

    This evaluation function is meant for use with adversarial search agents
    (not reflex agents).
    """
    return currentGameState.getScore()

class MultiAgentSearchAgent(Agent):
    """
    This class provides some common elements to all of your
    multi-agent searchers.  Any methods defined here will be available
    to the MinimaxPacmanAgent, AlphaBetaPacmanAgent & ExpectimaxPacmanAgent.

    You *do not* need to make any changes here, but you can if you want to
    add functionality to all your adversarial search agents.  Please do not
    remove anything, however.

    Note: this is an abstract class: one that should not be instantiated.  It's
    only partially specified, and designed to be extended.  Agent (game.py)
    is another abstract class.
    """

    def __init__(self, evalFn = 'scoreEvaluationFunction', depth = '2'):
        self.index = 0 # Pacman is always agent index 0
        self.evaluationFunction = util.lookup(evalFn, globals())
        self.depth = int(depth)

class MinimaxAgent(MultiAgentSearchAgent):
    """
    Your minimax agent (question 2)
    """

    def getAction(self, gameState: GameState):
        """
        Returns the minimax action from the current gameState using self.depth
        and self.evaluationFunction.

        Here are some method calls that might be useful when implementing minimax.

        gameState.getLegalActions(agentIndex):
        Returns a list of legal actions for an agent
        agentIndex=0 means Pacman, ghosts are >= 1

        gameState.generateSuccessor(agentIndex, action):
        Returns the successor game state after an agent takes an action

        gameState.getNumAgents():
        Returns the total number of agents in the game

        gameState.isWin():
        Returns whether or not the game state is a winning state

        gameState.isLose():
        Returns whether or not the game state is a losing state
        """
        "*** YOUR CODE HERE ***"
        maxVal = -float('inf')
        bestAction = None
        # 从吃豆人最初的位置，遍历所有可行的下一步
        for action in gameState.getLegalActions(0):
            value = self._getMin(gameState.generateSuccessor(0, action))
            if value is not None and value > maxVal:
                maxVal = value
                bestAction = action
        return bestAction
        
    def _getMax(self, gameState, depth = 0, agentIndex = 0):
        legalActions = gameState.getLegalActions(agentIndex)
        # 如果展开深度达到限制或者没有可行的下一步，则终止展开，并返回评价值
        if depth == self.depth or len(legalActions)==0:
            return self.evaluationFunction(gameState)
        # 否则就进行继续向下展开
        maxVal = -float('inf')
        # 对吃豆人下一步可行的操作进行遍历
        for action in legalActions:
            #agentIndex参数位置的值为1，表示从第一个鬼怪开始MIN遍历
            value = self._getMin(gameState.generateSuccessor(agentIndex, action), depth, 1)
            if value is not None and value > maxVal:
                maxVal = value
        return maxVal
    
    def _getMin(self, gameState, depth = 0, agentIndex = 1):
        # 获得鬼怪们的下一步合法操作，因为是一群鬼怪，所以MIN函数会反复调用
        legalActions = gameState.getLegalActions(agentIndex)
        if depth == self.depth or len(legalActions)==0:
            return self.evaluationFunction(gameState)
        minVal = float('inf')
        for action in legalActions:
            if agentIndex == gameState.getNumAgents() - 1:
                value = self._getMax(gameState.generateSuccessor(agentIndex, action), depth+1, 0)
            else:
                value = self._getMin(gameState.generateSuccessor(agentIndex, action), depth, agentIndex+1)
            if value is not None and value < minVal:
                minVal = value
        return minVal


        util.raiseNotDefined()

class AlphaBetaAgent(MultiAgentSearchAgent):
    """
    Your minimax agent with alpha-beta pruning (question 3)
    """

    def getAction(self, gameState: GameState):
        """
        Returns the minimax action using self.depth and self.evaluationFunction
        """
        "*** YOUR CODE HERE ***"
       # 从根节点开始展开，求MAX值，注意：返回值中下标为1的项才是行动内容
        return self._getMax(gameState)[1]
    def _getMax(self, gameState, depth = 0, agentIndex = 0, alpha = -float('inf'),
               beta = float('inf')):
        legalActions = gameState.getLegalActions(agentIndex)
        if depth == self.depth or len(legalActions)==0:
            return self.evaluationFunction(gameState), None
        # 遍历吃豆人可能的下一步
        maxVal = None
        bestAction = None
        for action in legalActions:
            # 考虑只有一个吃豆人的情况，直接求其MIN分支的评价值，agentIndex从1开始遍历所有鬼怪
            value = self._getMin(gameState.generateSuccessor(agentIndex, action), depth, 1, alpha, beta)[0]
            if value is not None and (maxVal == None or value > maxVal):
                maxVal = value
                bestAction = action
            if value is not None and value > beta:
                return value, action         
            if value is not None and value > alpha:
                alpha = value
        return maxVal, bestAction
    
    def _getMin(self, gameState, depth = 0, agentIndex = 0, alpha = -float('inf'),
               beta = float('inf')):       
        legalActions = gameState.getLegalActions(agentIndex)
        if depth == self.depth or len(legalActions)==0:
            return self.evaluationFunction(gameState), None
        # 遍历当前鬼怪可能的下一步
        minVal = None
        bestAction = None
        for action in legalActions:
            # 如果当前是最后一个鬼怪，那么下一轮就该是计算吃豆人的行为了，即调用MAX函数
            if agentIndex >= gameState.getNumAgents() - 1:
                value = self._getMax(gameState.generateSuccessor(agentIndex, action), depth+1, 0, alpha, beta)[0]
            else:
                # 如果不是最后一个鬼怪，则继续遍历下一个鬼怪，即agentIndex+1
                value = self._getMin(gameState.generateSuccessor(agentIndex, action), depth, agentIndex+1, alpha, beta)[0]
            if value is not None and (minVal == None or value < minVal):
                minVal = value
                bestAction = action
            # 按照α-β剪枝算法，如果v<α，则直接返回v
            if value is not None and value < alpha:
                return value, action
            # 按照α-β剪枝算法，更新β的值
            if value is not None and value < beta:
                beta = value
        return minVal, bestAction
class ExpectimaxAgent(MultiAgentSearchAgent):
    """
      Your expectimax agent (question 4)
    """

    def getAction(self, gameState: GameState):
        """
        Returns the expectimax action using self.depth and self.evaluationFunction

        All ghosts should be modeled as choosing uniformly at random from their
        legal moves.
        """
        "*** YOUR CODE HERE ***"
        total_agents = gameState.getNumAgents()

        def get_Max(gamestate, current_depth):
            actions_for_pacman = gamestate.getLegalActions(0)

            if current_depth > self.depth or gamestate.isWin() or not actions_for_pacman:
                return self.evaluationFunction(gamestate), None

            successors_score = []
            for action in actions_for_pacman:
                successor = gamestate.generateSuccessor(0, action)
                successors_score.append((get_Expect(successor, 1, current_depth)[0], action))

            return max(successors_score)

        def get_Expect(gamestate, agent_index, current_depth):
            actions_for_ghost = gamestate.getLegalActions(agent_index)
            if not actions_for_ghost or gamestate.isLose():
                return self.evaluationFunction(gamestate), None
            successors = [gamestate.generateSuccessor(agent_index, action) for action in actions_for_ghost]
            successors_score = []
            isPacman = agent_index == total_agents - 1
            for successor in successors:
                if isPacman:
                    successors_score.append(get_Max(successor, current_depth + 1))
                else:
                    successors_score.append(get_Expect(successor, agent_index + 1, current_depth))

            averageScore = sum(map(lambda x: float(x[0]) / len(successors_score), successors_score))
            return averageScore, None

        return get_Max(gameState, 1)[1]

        #util.raiseNotDefined()

def betterEvaluationFunction(currentGameState: GameState):
    """
    Your extreme ghost-hunting, pellet-nabbing, food-gobbling, unstoppable
    evaluation function (question 5).

    DESCRIPTION: <write something here so we know what you did>
    """
    "*** YOUR CODE HERE ***"
    newPos = currentGameState.getPacmanPosition()
    newFood = currentGameState.getFood()
    newGhostStates = currentGameState.getGhostStates()
    newScaredTimes = [ghostState.scaredTimer for ghostState in newGhostStates]
    walls = currentGameState.getWalls()

    # if not new ScaredTimes new state is ghost: return lowest value
    newFood = newFood.asList()
    ghostPos = [(G.getPosition()[0], G.getPosition()[1]) for G in newGhostStates]
    scared = min(newScaredTimes) > 0

    if currentGameState.isLose():
        return float('-inf')

    if newPos in ghostPos:
        return float('-inf')


    # if not new ScaredTimes new state is ghost: return lowest value

    closestFoodDist = sorted(newFood, key=lambda fDist: util.manhattanDistance(fDist, newPos))
    closestGhostDist = sorted(ghostPos, key=lambda gDist: util.manhattanDistance(gDist, newPos))

    score = 0

    fd = lambda fDis: util.manhattanDistance(fDis, newPos)
    gd = lambda gDis: util.manhattanDistance(gDis, newPos)

    if gd(closestGhostDist[0]) <3:
        score-=300
    if gd(closestGhostDist[0]) <2:
        score-=1000
    if gd(closestGhostDist[0]) <1:
        return float('-inf')

    if len(currentGameState.getCapsules()) < 2:
        score+=100

    if len(closestFoodDist)==0 or len(closestGhostDist)==0 :
        score += scoreEvaluationFunction(currentGameState) + 10
    else:
        score += (   scoreEvaluationFunction(currentGameState) + 10/fd(closestFoodDist[0]) + 1/gd(closestGhostDist[0]) + 1/gd(closestGhostDist[-1])  )

    return score

    #util.raiseNotDefined()


# Abbreviation
better = betterEvaluationFunction
